package com.cqs.leetcode;

import com.google.common.collect.Lists;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

/**
 * Created by cqs on 2018/3/24.
 */
public class SearchRotatedSortedArrayII {

    public boolean search(Integer[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (nums[mid] == target) return true;
            //左侧有序
            if (nums[left] < nums[mid]) {
                if (target > nums[mid]) {
                    left = mid + 1;
                } else {
                    if (nums[left] == target) return true;

                    if (nums[left] > target) {
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
            } else if (nums[left] == nums[mid]) {
                ++left;
            } else {//右侧有序
                if (nums[mid] < target) {
                    if (nums[nums.length - 1] == target) return true;
                    if (nums[nums.length - 1] > target) {
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                } else {
                    right = mid - 1;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {

        for (int k = 0; k < 1000; k++) {
            SearchRotatedSortedArrayII s = new SearchRotatedSortedArrayII();

            Random r = new Random();
            Set<Integer> set = new HashSet<>();
            int size = r.nextInt(10000)+1;
//            size = 10;
            int[] arr = new int[size];
            Integer[] arr2 = new Integer[size];
//            for (int i = 0; i < size; i++) {
//                int tmp = r.nextInt(size);
//                arr[i] = tmp;
////            set.add(tmp);
//            }
            int j = 0;
            while (j < size){
                int tmp = r.nextInt(size);
                if (set.contains(tmp)){
                    continue;
                }else {
                    arr[j] = tmp;
                    ++j;
                    set.add(tmp);
                }
            }
            Arrays.sort(arr);
            int pivot = r.nextInt(size);

            for (int i = 0; i < pivot; i++) {
                arr2[i] = arr[size - pivot + i];
            }
            for (int i = pivot; i < size; i++) {
                arr2[i] = arr[i - pivot];
            }
            Integer[] arr3 = {6, 7, 8, 9, 0, 1, 2, 3, 4, 5};
//            arr2 = arr3;
            set.addAll(Lists.newArrayList(arr2));
//            System.out.println(Lists.newArrayList(arr2));
            MinimumRotatedSortedArray m = new MinimumRotatedSortedArray();
            int min = m.findMin(arr2);
            Integer[] arr0 = Arrays.copyOf(arr2, arr2.length);
            Arrays.sort(arr0);
            if (min != arr0[0]) {
                System.out.println(Lists.newArrayList(arr2));
                System.out.println("min:" + min + "\t arr[0]" + arr0[0]);
            }
            ;
//            for (int i = 0; i < size; i++) {
////            System.out.println(i + "\t" + s.search(arr, i));
//                boolean inset = set.contains(i);
//                boolean inArr = s.search(arr2, i);
//                if (inArr != inset) {
//                    System.err.println(i + "\t" + inset + "\t" + inArr);
//                } else {
////                System.out.println(i + "\t" + inset + "\t" + inArr);
//                }
//            }
        }

    }

}
